﻿\documentclass{esannV2}
\usepackage[ruled,vlined,portugues]{algorithm2e}
\usepackage[brazil]{babel} 
\usepackage{graphicx}
\usepackage[utf8]{inputenc}
\usepackage{amssymb,amsmath,array}
\voffset 0 cm \hoffset 0 cm \addtolength{\textwidth}{0cm}
\addtolength{\textheight}{0cm}\addtolength{\leftmargin}{0cm}
\begin{document}
\title{Aprendizagem de máquina usando Floresta de Caminhos Ótimos}
\author{Willian Paraguassu Amorim$$
}
\maketitle

\section{Introdução}

Reconhecimento de padrões pode ser definido coma a classificação de dados baseado no conhecimento adquirido ou na extração de informações estatísticas de padrões (representações), e tem como objetivo procurar por regras de decisão, que possa maximizar a separação entre classes de classificação. Dado um padrão, o reconhecimento ou classificação consiste em dividir o problema em uma das seguintes categorias: classificação supervisionada em que o padrão de entrada é identificado como um membro de uma classe pré-definida, classificação não supervisionado em que o padrão de entrada é atribuído a uma classe até então desconhecida, também conhecida como o agrupamento de amostras por padrões semelhantes, e classificação semi-supervisionada, onde somente uma parte do conjunto de entrada, possui classe pré-definida \cite{DudaHartStork01}.

Muitas das principais abordagens na área de aprendizagem e reconhecimento de padrões são baseadas na análise estatística. Nesse modelo, cada padrão é representado em condições de $d$ espaço de atributos e visualizado em um espaço d-dimensão. Com isso, o objetivo é escolher aquelas características que permitem que vetores de padrão pertencentes a diferentes categorias possam ocupar regiões compactas e disjuntas em um espaço de características d-dimensão. A eficácia do espaço de representação é determinada pela forma como os padrões de diferentes classes podem ser separadas \cite{bookPRTom}. Técnicas simples na abordagem estatística podem lidar facilmente com classes linearmente separáveis como apresentado na Figura \ref{featureSpaces}(a), mas para representações pricewise, requerem técnicas mais robustas como Redes Neurais Artificiais. Na prática, infelizmente muitas aplicações envolve classes lineamente não separáveis, como apresentado na Figura \ref{featureSpaces}(c). Alguns exemplos de possíveis soluções são Máquinas de Vetores de Suporte (SVM)\cite{Boser92atraining}, e o algoritmo clássico k-nearest neighbors\cite{Laaksonen96classificationwith}. 

\begin{figure}[!htbp]
\begin{center}
$ \begin{array}{ccc}
\includegraphics[scale=0.30]{a.jpg} &
\includegraphics[scale=0.30]{b.jpg} &
\includegraphics[scale=0.30]{c.jpg} \\
(a) & (b) & (c)
\end{array} $
\caption{Examples of some feature spaces: (a) Linearly separable. (b) Piecewise linearly separable. (c) Non separable.}
\label{featureSpaces}
\end{center} 
\end{figure}

No entanto, mesmo pelos trabalhos consolidados na área, para resolver tais problemas de maneira eficiente, umas das características mais importantes no espaço amostral não possuem tanta atenção na classificação supervisionada, que é a relação de conectividade no espaço de amostras. Alguns trabalhos recentes \cite{papaOPF}\cite{rochaOPF}, vêm apresentando bons resultados no processo de aprendizagem supervisionada e não supervisionada utilizando a técnica OPF. A técnica OPF, é um classificador supervisionado de aplicação geral, particularmente eficiente na classificação de imagens. O classificador OPF reduz problemas de classificação de padrões para um problema de particionamento em um grafo induzido, pelo conjunto de dados.

Nossa proposta de Doutorado, será buscar por novas soluções na área de aprendizado de máquina, criando novas heuristicas e modelos de classificação de dados usando Floresta de Caminhos Ótimos. A primeira fase desse trabalho,  já foi desenvolvida, a qual foi criação uma nova técnica chamada OPF-LA. A técnica OPF-LA, explora o modelo de classificadores supervisionados OPF, sugerindo uma modificação no formato de treinamento dos dados para classificação, diferente assim da heurística proposta por Papa\cite{papaOPF}. Essa nova técnica tem como objetivo analisar os dados localmente por classe, e realizar a seleção de protótipos a partir da heurística da menor distância acumulada de um vértice aos demais vértices adjacentes. 

O processo segue um modelo no formato de varredura sobre todas as amostras de sua respectiva classe, acumulando o valor de menor distância para cada vértice adjacente. Também criamos uma generalização da técnica OPF-LA, que pode ampliar o número de protótipos para representação de cada classe de classificação, aumentando assim o espaço de possibilidade para controle dos dados de classificação independente de aplicação. Atualmente, a técnica passa por ajustes, e experimentos sobre imagens de textura complexa, como classificação de defeitos em Couro Bovino. Estamos também, iniciando o processo de elaboração de um primeiro artigo, apresentando a nova heurística OPF-LA, e os resultados experimentais comparando com técnicas tradicionais na área como a técnica OPF-grafo completo e Máquinas de Vetores de Suporte(SVM).

\subsection{Objetivos}

\subsubsection{Geral}

Dentro do contexto do problema apresentado, a proposta desse trabalho de doutorado, tem como objetivo a criação de novas técnicas de aprendizagem e classificação de dados, usando Floresta de Caminhos Ótimos. Estaremos também buscando por novas representações de dados, com o uso de árvores filogenéticas, que poderão ampliar a eficiência na classificação de dados, em conjunto às novas propostas a serem desenvolvidas. 

\subsubsection{Específicos}

\begin{enumerate} 

\item Estudo de grafos;
\item Estudo de grafos como ferramenta de Representação de Imagens;
\item Estudo de grafos e Reconhecimento de Padrões;
\item Estudo de Reconhecimento Estrutural de Padrões e grafos relacionais;
\item Estudo da Técnica Transforma Imagem Floresta (Algoritmos e Aplicações);
\item Identificação dos principais problemas e propostas de soluções na aplicação de grafos em Reconhecimento de Padrões;
\item Estudo da técnica Floresta de Caminhos Ótimos-OPF nos modelos de aprendizagem supervisionado e não supervisionado;
\item Encontrar possíveis melhorias na técnica OPF supervisionada;
\item Criação de novas propostas baseado em OPF, no aprendizado supervisionado e semi-supervisionado;
\item Implementação das novas técnicas propostas;
\item Seleção de problemas na área de reconhecimento de padrões e realização de experimentos;
\item Estudo de Árvores Filogenéticas;
\item Criação de uma proposta de representação de dados usando Árvores Filogenéticas;
\item Experimentos com os novos classificadores em conjunto com Árvores Filogenéticas;
\item Análise dos resultados e possíveis modificações;
\item Criação de artigos a partir dos resultados obtidos;

\end{enumerate}

\section{Floresta de Caminhos Ótimos - OPF}

O problema de reconhecimento de padrões pode ser modelado para o uso de floresta de caminhos ótimos em um grafo, definido em seu espaço de atributos. Os nós são as amostras, sendo representadas pelos seus respectivos vetores de atributos, e os arcos definidos por uma relação de adjacência entre as amostras \cite{rit01}\cite{rit02}. Tanto os nós quanto os arcos, podem ser ponderados, tendo a possibilidade de aplicação de diversas funções de custo. Com isso, é possível o particionamento do grafo em árvores de caminhos ótimos, sendo enraizadas pelos seus respectivos protótipos (sementes) na fase de treinamento, e a classificação de uma amostra qualquer sendo o mesmo rótulo do protótipo mais fortemente conexo. A seguir apresentaremos a técnica OPF, seguindo a heurística de análise dos dados sobre um grafo completo e seleção dos protótipos como sendo as amostras mais próximas de classes distintas.

\subsection{Definição}

O cálculo de caminhos ótimos para as demais amostras são computadas pelo algoritmo de Transformada Imagem Floresta (IFT)\cite{FalcaoTPAMI04}. A tecnica IFT é essencialmente o algoritmo de Dijkstra, modificado para receber várias fontes e aplicação de outras funções de custo. Seu comportamento inicialmente identifica os mínimos da função de custo como os nós de origem e se propaga em ordem não decrescente a fim de melhores caminhos, particionando o grafo em uma floresta de caminhos ótimos onde as raízes são os protótipos selecionados.
Atualmente Papa\cite{papaOPF}, apresentou um novo modelo de classificador supervisionados baseado em OPF. A técnica usa como modelo de relação de adjacência um grafo de conexão completa, uma função de custo $f_{max}$, dada pela Equação \ref{eqFMAX}, e escolhe os protótipos a partir da árvore resultante gerada pela técnica Minimum Spanning Tree (MST). 

\begin{equation}
f_{max}(\pi_s . \langle s \rangle) = max\{f_{max}(\pi_s),d(s,t)\},
\label{eqFMAX}
\end{equation}

\subsection{Classificador OPF baseado em grafo completo}

Dado ($Z_1$,$A_1$), ($Z_2,A_1$) and ($Z_3$,$A_1$) grafos completos, representando as amostras de treinamento, avaliação e classificação respectivamente, como apresentado na Figura \ref{pixelCentral}(a). Seja $\lambda(s)$ um função que atribui o rótulo correto $i$ $\{1,2,...,c\}$ da classe $i$ para qualquer amostra $s$ $\in$ $Z_1$ $\cup$ $Z_2$ $\cup$ $Z_3$, $S$ um conjunto de protótipos de todas as classes, sendo $S$ $\subset$ $Z_1$, e $v$ um algoritmo que extrai $n$ atributos como: textura, cor, formas geométricas) de qualquer amostra $s$ $\in$ $Z_1$ $\cup$ $Z_2$ $\cup$ $Z_3$ retornando um vetor $\vec{v}(s)$. A distância $d(s,t)\geq 0$, entre duas amostras, $s$ e $t$, é somente um valor entre os vetores de características $\vec{v}(s)$ e $\vec{v}(t)$. Pode-se usar qualquer função distância, mas para a abordagem de Papa\cite{papaOPF} sobre grafo completo, se utiliza distância Euclediana $\mid \mid \vec{v}(t)$ - $\vec{v}(s) \mid \mid$.

\begin{figure}[!htbp]
\begin{center}
$ \begin{array}{ccc}
\includegraphics[scale=0.21]{2a.jpg} &
\includegraphics[scale=0.21]{2b.jpg} &
\includegraphics[scale=0.21]{2c.jpg} \\
(a) & (b) & (c)
\end{array} $
$ \begin{array}{ccc}
\includegraphics[scale=0.21]{2d.jpg} &
\includegraphics[scale=0.21]{2e.jpg} &
\includegraphics[scale=0.21]{2f.jpg} \\
(d) & (e) & (f)
\end{array} $

\caption{(a) Grafo completo ponderado nas arestas. (b) Grafo MST referente ao grafo completo. (c) Protótipos selecionados a partir da heurística de elementos adjacentes de classes distintas na MST. (d) Amostra de teste e suas conexões em todos os elementos do grafo de treinamento. (e) Caminho ótimo do protótipo mais fortemente conexo. (f) Permanência da amostra anterior classificada, e inclusão de uma nova amotra para classificação.}
\label{pixelCentral}
\end{center} 
\end{figure}

O problema de classificação nada mais é do que rotular a classe correta $\lambda(s)$, para qualquer amostra $s$ $\in$ $Z_3$. A fase de treinamento consiste em encontrar um subgrupo de protótipos $S^{*}$ $\subset$ $Z_1$, e a classificação de qualquer amostra $s$ $\in$ $Z_3$, é feita através da avaliação de forma incremental atribuindo a ele o 
rótulo do protótipo mais fortemente conexo. 

\subsection{Fase de Treinamento}

Dado um grafo completo $(Z_1,A)$ o treinamento consiste em encontrar protótipos para $S^{*}$, através da Árvore Geradora Mínina (MST) e Floresta de Caminhos Ótimos com raízes em $S^{*}$. Assumindo que conhecemos o conjunto $S*$, o Algoritmo 1 de Floresta de Caminhos Ótimos (FCO), propaga os rótulos dos protótipos para todas as amostras de suas respectivas árvores de caminhos ótimos, formando um mapa de rótulos $L(s)$ $\in$ $\{1,2,...,c\}$.
\incmargin{1em}
\linesnumbered
\begin{algorithm}
\caption{Algoritmo FCO}
\Entrada{Conjunto Z, protótipos $S*$ $\subset$ $Z$ e o par $(v,d)$ para extração de características e cálculos de distâncias.}
\Saida{Floresta de caminhos ótimos P, mapa de valores ótimos V, e mapa de rótulos L.}
\Dados{Fila Q de prioridades e variável tmp}
\BlankLine
\ParaCada{s $\in$ $Z/ \ S*$}
{
$V(s)\longleftarrow +\infty,$
}
\ParaCada{s $\in$ $ S*$}
{
$V(s)\longleftarrow 0,$
$P(s)\longleftarrow nil,$
$L(s)\longleftarrow \lambda(s),$
e insira s em Q.
}
\Enqto{Q não estiver vazia}
{
Remova de Q uma amostra $s$ tal que V(s) seja mínimo. \\
\ParaCada{t $\in$ Z tal que $t \neq s$ e $V(t)>V(s)$}
{
Calcule tmp $\longleftarrow$ $max\{V(s), d(s,t)\}$.\\
\Se{$tmp < V(t)$}
{
\Se{V(t) $\neq$ $+\infty$}
{
Remova t de Q.
}
$P(t)\longleftarrow s, L(t)\longleftarrow L(s), V(t)\longleftarrow tmp.$ Insira t em Q.
}
}
}
\Retorna{P,R,V}
\label{algorithmOPF}
\end{algorithm}
\decmargin{1em}

O processo de treinamento do classificador supervisionado baseado em Floresta de Caminhos Ótimos, usando grafo completo Figura \ref{pixelCentral}(a), consiste em encontrar um conjunto de protótipos $S^{*}$, de modo que os elementos sejam considerados os mais representativos. Várias heurísticas podem ser adotadas, entretanto o modo de seleção pode afetar o desempenho do classificador. Um processo de seleção sugerido por \cite{papaOPF}, para seleção de protótipos sobre grafos completos, é o uso do grafo gerado sobre um $MST$ (Árvore Geradora Mínima). Computando uma $MST$ no grafo completo $(Z,A)$ Figura \ref{pixelCentral}(b), obtemos um grafo conexo acíclico, cujos nós são todas as amostras em $Z_1$, e os arcos são não direcionados e ponderados. A soma dos pesos de seus arcos é mínima, se comparada a outras árvores geradoras no grafo completo, com isso obtemos uma árvore geradora ótima. Dessa forma, os protótipos a serem selecionados, são os elementos mais próximos de classes diferentes Figura \ref{pixelCentral}(c). Removendo-se os arcos entre as classes diferentes, essas amostras adjacentes serão os protótipos em $S^{*}$. Um ponto importante, é que uma classe pode conter vários protótipos (árvore de caminhos ótimos), mas devemos sempre garantir que toda classe, deva ter no mínimo um protótipo. O Algoritmo 2, apresenta uma modificação sobre o Algoritmo 1, para calcular uma árvore de peso mínimo $MST$, e selecionar os protótipos para $S*$, apresentando semelhanças ao algoritmos de $Prim$.

\incmargin{1em}
\linesnumbered
\begin{algorithm}
\caption{Algoritmo MST}
\Entrada{Conjunto Z, par $(v,d)$ para extração de características e cálculos de distâncias}
\Saida{Árvore de peso mínimo P, mapa de valores V e protótipos $S*$}
\Dados{Fila Q de prioridades, status() e variável tmp}
\BlankLine
\ParaCada{s $\in$ Z/$t_0$}
{
$V(s)\longleftarrow +\infty,$
$status(s)\longleftarrow 0.$
}
V($t_0$)$\longleftarrow$ 0, P($t_0$)$\longleftarrow$ nil, status($t_0$)$\longleftarrow$ 1, e insira $t_0$, em Q.\\
\Enqto{Q não estiver vazia}
{
Remova de Q uma amostra s tal que V(s), é mínimo e faça status(s)$\longleftarrow$ 2.\\
\Se{P(s) $\neq$ nil}
{
\Se{$\lambda(s)$ $\neq$ $\lambda(P(s))$}
{
$S*$ $\longleftarrow$ $S*$ $\cup$ $\{s,P(s)\}$
}
}
\ParaCada{t $\in$ Z tal que $t\neq s$ e $status(t)\neq 2$}
{
Calcule tmp $\longleftarrow$ d(s,t). \\
\Se{$tmp < V(t)$}
{
\Se{status(t) = 1}
{
Remova t de Q.
}
P(t) $\longleftarrow$ s e V(t) $\longleftarrow$ tmp.
\\
Insira t em Q e faça $status(t)\longleftarrow 1$.
}
}
}
\label{algorithmMST}
\end{algorithm}
\decmargin{1em}

\subsection{Fase de Classificação}

A classificação de uma nova amostra $t$, considera todas as conexões entre $t$ e as amostras $s$ de treinamento, como se $t$ fizesse parte do grafo original. A partir de todos os possíveis caminhos entre o conjunto $S$ até $t$, o objetivo na classificação está em encontrar o caminho ótimo $P*(t)$, de $S$ até $t$, com a classe $\lambda(R(t))$ de seu protótipo R(t) $\in$ S, mais fortemente conexo. O caminho pode ser encontrado incrementalmente, avaliando o valor de custo ótimo $V(t)$, pela Equação \ref{eqClassificacao} aplicado $\forall s$ $\in$ Z.

\begin{equation}
V(t) = min\{max\{V(s),d(s,t)\}\}.
\label{eqClassificacao}
\end{equation}

Seja $s*$ $\in$ Z, que satisfaz a Equação \ref{eqClassificacao}, (predecessor P(t) = $s*$). Dado que $L(s*)$ = $\lambda(R(t))$, classificação é realizada associando o rótulo de $L(s*)$ com sendo a classe de $t$. O erro de classificação ocorre quando $L(s*)$ $\neq$ $\lambda(t)$.

\section{Metodologia}

Para o inicio do desenvolvimento desse trabalho, vários conceitos na área de grafos e modelos de aprendizagem terão que ser pesquisados. Estaremos nos organizando para documentar todos os trabalhos já desenvolvidos na área, e propondo novas heurísticas e técnicas, que possam otimizar o processo de treinamento e classificação de dados, tanto em problemas na área supervisionada quanto semi-supervisionada.

\section{Resultados Esperados}

A proposta aqui sugerida como tema de trabalho de Doutorado, vem criar novas abordagens na área de aprendizagem de máquina, usando Floresta de Caminhos Ótimos, e representação de dados usando Árvores Filogenéticas. Esperamos criar novas técnicas na área, que possa otimizar resultados na classificação de dados, comparados assim com abordagens tradicionais na área. Acreditamos que a partir dos resultados alcançados, poderemos aumentar a divulgação do uso de Floresta de Caminhos Ótimos no processo aprendizagem, e classificação de dados, além também de novas áreas de aplicação. Estaremos buscando realizar experimentos na área de biotecnologia, em aplicações como monitoramento de larvas, contagem e classificação de leveduras no processo de geração do etanol, classificação de grão de polén, reconhecimento de faces e também o uso de OPF e das novas técnicas criadas na área de biologia computacional.


\section{Cronograma de Execução}

\bibliographystyle{unsrt}
\bibliography{biblio}
\end{document}

